package algorithms;

public class SerialQuickSort implements SortStrategy{
    private int[] data;
    private int[] ret;
    private int dataLength;

    public SerialQuickSort() {
        ;
    }

    public int[] sort(int[] data) {
        this.data = data.clone();
        this.dataLength = this.data.length;
        this.ret = new int[this.dataLength];

        _sort(0, this.dataLength-1);
        return this.data;
    }

    private void _sort(int l, int r) {
        if (l >= r) return;
        int q = _partition(l ,r);
        _sort(l, q-1);
        _sort(q+1, r);
    }

    private int _partition(int l, int r) {
        int q = l;
        int pivot = this.data[r];
        for (int i=l; i<r; i++) {
            if (this.data[i] < pivot) {
                int tmp = this.data[i];
                this.data[i] = this.data[q];
                this.data[q] = tmp;
                q ++;
            }
        }
        int tmp = this.data[q];
        this.data[q] = this.data[r];
        this.data[r] = tmp;

        return q;
    }
}
